package cxydmmszl.chapter03.t033;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.StreamTokenizer;

/**
 * <li style="color: red;">Prob</li>
 * 打印二叉树的边界节点
 * <li style="color: red;">Desc</li>
 * 给定一颗二叉树的根节点 root，按照如下两种标准分别实现二叉树的边界节点的逆时针打印。<br/>
 * 标准一：<br/>
 * 1，根节点为边界节点。<br/>
 * 2，叶节点为边界节点。<br/>
 * 3，如果节点在其所在的层中是最左的或最右的，那么该节点也是边界节点。<br/>
 * 标准二：<br/>
 * 1，根节点为边界节点。<br/>
 * 2，叶节点为边界节点。<br/>
 * 3，树左边界延伸下去的路径为边界节点。<br/>
 * 4，树右边界延伸下去的路径为边界节点。<br/>
 * ps:具体请对照样例<br/><br/>
 * 输入描述：<br/>
 * 第一行输入两个整数 n 和 root，n 表示二叉树的总节点个数，root 表示二叉树的根节点。
 * 以下 n 行每行三个整数 fa，lch，rch，表示 fa 的左儿子为 lch，右儿子为 rch。(如果 lch 为 0 则表示 fa 没有左儿子，rch同理)<br/><br/>
 * 输出描述：<br/>
 * 输出两行整数分别表示按两种标准的边界节点。
 * <li style="color: red;">Link</li> CD162
 *
 * @author habitplus
 * @since 2021-08-30 10:24
 */
public class Main {

    public static void main(String[] args){
        int n = nextInt(), r = nextInt();
        TreeNode root = build();
        print1(root);
        System.out.println();
        print2(root, new StringBuilder());
    }

    private static final StreamTokenizer st = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
    private static int nextInt(){
        try{
            st.nextToken();
            return (int)(st.nval);
        }
        catch(IOException e){
            throw new RuntimeException(e);
        }
    }

    public static TreeNode build(){
        int fa = nextInt();
        int lch = nextInt();
        int rch = nextInt();
        TreeNode root = new TreeNode(fa);
        if(lch != 0){
            root.left = build();
        }
        if(rch != 0){
            root.right = build();
        }
        return root;
    }


    public static void print1(TreeNode root){
        if(root == null){
            return;
        }
        StringBuilder sb = new StringBuilder();
        int height = getHeight(root, 0);
        TreeNode[][] edgeNode = new TreeNode[height][2];
        setEdgeNode(root, 0, edgeNode);
        for (TreeNode[] treeNodes : edgeNode) {
            sb.append(treeNodes[0].value).append(" ");
        }
        leafInNode(root, 0, edgeNode, sb);
        for(int i = edgeNode.length - 1; i >= 0; --i){
            if(edgeNode[i][0] != edgeNode[i][1]){
                sb.append(edgeNode[i][1].value).append(" ");
            }
        }
        System.out.print(sb);
    }

    public static int getHeight(TreeNode root, int h){
        if(root == null){
            return h;
        }
        return Math.max(getHeight(root.left, h + 1), getHeight(root.right, h + 1));
    }

    public static void setEdgeNode(TreeNode root, int h, TreeNode[][] edgeNode){
        if(root == null){
            return;
        }
        edgeNode[h][0] = edgeNode[h][0] == null ? root : edgeNode[h][0];
        edgeNode[h][1] = root;
        setEdgeNode(root.left, h + 1, edgeNode);
        setEdgeNode(root.right, h + 1, edgeNode);
    }

    public static void leafInNode(TreeNode root, int h, TreeNode[][] edgeNode, StringBuilder sb){
        if(root == null){
            return;
        }
        if(root.left == null && root.right == null && root != edgeNode[h][0] && root != edgeNode[h][1]){
            sb.append(root.value).append(" ");
        }
        leafInNode(root.left, h + 1, edgeNode, sb);
        leafInNode(root.right, h + 1, edgeNode, sb);
    }

    //---------------------------------------------------------------------------------

    public static  void print2(TreeNode root, StringBuilder sb){
        if(root == null){
            return;
        }
        sb.append(root.value).append(" ");
        if(root.left != null && root.right != null){
            printLeftEdge(root.left, true, sb);
            printRightEdge(root.right, true, sb);
        }
        else{
            print2(root.left != null ? root.left : root.right, sb);
        }
        System.out.print(sb);
    }

    public static void printLeftEdge(TreeNode root, boolean print, StringBuilder sb){
        if(root == null){
            return;
        }
        if(print || (root.left == null && root.right == null)){
            sb.append(root.value).append(" ");
        }
        printLeftEdge(root.left, print, sb);
        printLeftEdge(root.right, print && (root.left == null), sb);
    }

    public static void printRightEdge(TreeNode root, boolean print, StringBuilder sb){
        if(root == null){
            return;
        }
        printRightEdge(root.left, print && root.right == null, sb);
        printRightEdge(root.right, print, sb);
        if(print || (root.left == null && root.right == null)){
            sb.append(root.value).append(" ");
        }
    }

    private static class TreeNode{
        int value;
        TreeNode left;
        TreeNode right;
        public TreeNode(int value){
            this.value = value;
        }
    }

}


